This invention relates generally to computer systems and more particularly to a method and apparatus for performing method lookup to support transitive method override in the presence of modularity constructs, such as packages.
Inheritance is a major property of most object oriented programming systems. With inheritance, when a class is declared as a subclass of a superclass, that subclass automatically inherits all of the methods and attributes of the superclass. Thus, if class A has method M1 and attribute AT1, then class B, which is a subclass of class A, automatically inherits method M1 and attribute AT1. In addition to inheriting the methods and attributes of the superclass, the subclass may further comprise additional methods and attributes. Thus, for the example given above, class B may further comprise methods M2 and M3, and attributes AT2 and AT3.
In addition to inheriting and adding methods and attributes, some object oriented systems further allow subclasses to override the methods of the superclass. That is, the subclass is allowed to provide an implementation for an inherited method which is different from that provided by the superclass. This means that, for the example given above, subclass B may provide a different implementation for method M1 than that provided by superclass A. For example, the implementation for M1 provided by superclass A may draw a square whereas the implementation for method M1 provided by subclass B draws a circle. Thus, even though both methods have the same name, they may have different implementations. Which implementation is invoked depends upon the class of the object instance on which the method is invoked. If the method is invoked on a class A instance, then the implementation provided by class A will be invoked. If the method is invoked on a class B instance, then the implementation provided by class B will be invoked. Because there may be multiple implementations for any particular method, a determination will have to be made at runtime as to which implementation to invoke. The process of selecting which implementation to invoke at runtime is referred to as dynamic method dispatch.
In single inheritance systems where every subclass is able to access, and hence, override every method of a higher level class, the dynamic method dispatch process is relatively straightforward. However, some systems, such as the Java(trademark) programming system manufactured by Sun Microsystems, Inc. of Mountain View, Calif., implement constructs known as xe2x80x9cmodularity constructsxe2x80x9d which make it possible for a developer to restrict the accessibility of certain methods of certain classes to other classes. In the face of these accessibility restrictions, dynamic method dispatch is made much more complicated.
To elaborate, a modularity construct, sometimes referred to as a xe2x80x9cpackagexe2x80x9d in Java(trademark), provides a mechanism for grouping or encapsulating selected classes. The package construct makes it possible to limit access to the classes within a package by classes in other packages. More specifically, each method of each class within a package may be declared as xe2x80x9cpublicxe2x80x9d, xe2x80x9cprotectedxe2x80x9d, or xe2x80x9cpackage privatexe2x80x9d. If a method is declared public or protected (denoted as public/protected hereinafter), then it may be accessed, and hence overridden, by any subclass of that class. On the other hand, if a method is declared package private, then that method may be accessed and overridden by a subclass if and only if that subclass is within the same package. Subclasses outside the package may not access or override the method. FIG. 1 illustrates an example of such a situation. In FIG. 1, there is shown two packages, P1 and P2. Package P1 contains a class A having a package private method M1. Package P2 contains a class B which extends A (meaning that B is a subclass of A) having a public/protected method M1. Because method M1 of class A is declared package private, and because class B is not in the same package as class A, class B will not be able to access or to override the method M1 of class A. Note that the package construct does not prevent class B from being a subclass of A, and hence, inheriting all of the attributes and methods of class A. The package only prevents class B from overriding the method M1 of class A. To enforce package constraints, it is a general rule that unless a subclass is within the same package as a higher level class that it wishes to override, it cannot override a package private method of the higher level class.
While on the surface, this general rule appears to effectively enforce the accessibility constraints imposed by modularity constructs, it can lead to some undesirable results, one of which is that of non-transitive method override. To illustrate how this non-transitive result can arise, suppose that a structure such as that shown in FIG. 2 is created, wherein there are two packages, P1 and P2. In package P1, there is a class A having a package private method M1. In the same package, there is a subclass B which extends A, having a public/protected method M1. In package P2, there is a subclass C which extends B, and which has a public/protected method M1. With such a structure, it is clear that method M1 of subclass B can access and hence override method M1 of class A (since B is in the same package as A). It is also clear that method M1 of class C can override the method M1 of class B (since method M1 of B is declared to be public/protected). According to the transitive property, if method M1 of C can override method M1 of B, and method M1 of B can override method M1 of A, then method M1 of C should be able to override method M1 of A. This is not the result in this example, however, because under the rule set forth above, M1 of C cannot override M1 of A because M1 of A is package private and C is not in the same package as A. Thus, as this example shows, strict adherence to this rule can lead to non-transitive results. Because this is a somewhat non-intuitive result, and because transitive method override is a desirable property, there is a need for an improved dynamic method dispatch mechanism which is both capable of enforcing the accessibility constraints of modular constructs and providing transitive method override.
One mechanism that may be used to perform dynamic method dispatch is a method lookup mechanism. In the present invention, there is provided an improved method lookup mechanism which not only enforces accessibility constraints imposed by modularity constructs but also enables transitive method override.
According to one embodiment of the present invention, when a method m is invoked on a target object, the resolved method m in a resolved class is checked to determine whether it has been declared as public/protected. If so, then standard method lookup may be used to determine the proper implementation of method m to invoke. However, if the resolved method is not declared as public/protected, then a path stack is constructed. The path stack provides a listing of the class hierarchy between the target object and the resolved class.
Once constructed, the path stack is used to determine which implementation of method m to invoke in response to the method invocation. Specifically, the resolved method m is initially set as the candidate method to invoke. Then a downward search is performed through the classes on the path stack. At each class on the path stack, a determination is made as to whether that class: (1) provides an implementation for the method m; (2) can access the resolved method; and (3) has declared the method m as public/protected. If so, then the proper implementation for method m to be invoked may be determined using standard method lookup. However, if a class satisfies only the first two criteria, then the implementation for method m provided by that class is made the new candidate method, and the process loops back to test the next class on the path stack, This loop continues until either a class is found which satisfies all three criteria, in which case standard method lookup is used to invoke the proper implementation for method m, or until all of the classes on the path stack have been tested, in which case the last detected candidate method is invoked. Performing method lookup in this manner will enable accessibility constraints imposed by modularity constructs to be enforced while at the same time enabling method override to be transitive. dr
FIG. 1 is a diagram of two classes within two packages to illustrate the accessibility constraints that may be imposed by modularity constructs.
FIG. 2 is a diagram of three classes within two packages to illustrate how enforcement of modularity constraints may cause method override to be non-transitive.
FIG. 3 is a diagram of a sample class hierarchy to illustrate the manner in which the standard method lookup methodology carries out dynamic method dispatch.
FIG. 4 is a diagram of a sample class hierarchy for use in facilitating description of the present invention.
FIG. 5 is a diagram of a sample path stack for the class hierarchy shown in FIG. 4 to facilitate description of the present invention.
FIGS. 6a-6b are flow diagrams for the method of the present invention.
FIG. 7 is a hardware block diagram of a computer system in which an embodiment of the present invention may be implemented.